#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);++i)
#define ForDown(i,j,k) for(int i=(j);i>=(k);--i)
#define Debug(fmt, args...) fprintf(stderr,"(func %s, line #%d): " fmt,__func__,__LINE__,##args),fflush(stderr)
#define debug(fmt, args...) fprintf(stderr,fmt,##args),fflush(stderr)
#define within :
#define LJY main
using namespace std;
typedef long long ll;
const int N=4e5+5;
inline ll read(){
  char ch=getchar();ll x=0,f=1;
  while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9')
    x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
  return x*f;
}
int n;vector<ll>lis;
ll s[N],t[N];pair<ll,ll>lim[N];
void solve1(){
  For(i,1,n){
    ll x=read();
    auto it=lower_bound(lis.begin(),lis.end(),x);
    if(it==lis.end()||*it!=x) lis.emplace(it,x);
    else lis.erase(it);
    int len=lis.size();
    For(i,0,len-1) s[i+1]=s[i]+lis[i];
    For(i,1,len) lim[i]={s[i],s[len]-s[len-i]};
    ll nowL=0,nowR=0,ans=0;
    For(i,1,len){
      if(lim[i].first>nowR){
        ans+=nowR-nowL;
        nowL=lim[i].first,nowR=lim[i].second;
      }else nowR=lim[i].second;
    }ans+=nowR-nowL;
    printf("%lld\n",ans);
  }
}
set<ll>st;
void solve2(){
  ll sum=0;
  For(i,1,n){
    ll x=read();
    auto it=st.find(x);
    if(it==st.end()) st.emplace(x),sum+=x;
    else st.erase(it),sum-=x;
    int len=st.size();
    if(len<=120){
      int i=0;
      for(ll x within st) s[i+1]=s[i]+x,i++;
      For(i,1,len) lim[i]={s[i],s[len]-s[len-i]};
      ll nowL=0,nowR=0,ans=0;
      For(i,1,len){
        if(lim[i].first>nowR){
          ans+=nowR-nowL;
          nowL=lim[i].first,nowR=lim[i].second;
        }else nowR=lim[i].second;
      }ans+=nowR-nowL;
      printf("%lld\n",ans);
    }else{
      auto it=st.begin();
      For(i,0,60) s[i+1]=s[i]+*(it++);
      auto it=--st.end();
      For(i,0,60) t[i+1]=t[i]+*(it++);
      For(i,1,60) lim[i]={s[i],t[i]};
      ll nowL=0,nowR=0,ans=0;
      For(i,1,59){
        if(lim[i].first>nowR){
          ans+=nowR-nowL;
          nowL=lim[i].first,nowR=lim[i].second;
        }else nowR=lim[i].second;
      }ans+=sum-nowL;
      printf("%lld\n",ans);
    }
  }
}
signed LJY(){
  freopen("kte.in","r",stdin);
  freopen("kte.out","w",stdout);
  n=read();
  if(n<=3000) solve1();
  else solve2();
  return 0;
}